/*
 * @Author: szx
 * @Date: 2021-11-16 13:13:55
 * @LastEditTime: 2021-12-28 16:16:30
 * @Description:
 * @FilePath: \leetcode\1-99\90\90.js
 */
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
// var subsetsWithDup = function (nums) {
//     nums.sort((a, b) => a - b);
//     const res = [];
//     const tmp = [];
//     const n = nums.length;
//     const dfs = (flag, i) => {
//         if (i === n) {
//             res.push(tmp.slice());
//             return;
//         }
//         dfs(false, i + 1);
//         if (!flag && i > 0 && nums[i - 1] === nums[i]) {
//             return;
//         }
//         tmp.push(nums[i]);
//         dfs(true, i + 1);
//         tmp.pop(n - 1);
//     };
//     dfs(false, 0);
//     return res;
// };

var subsetsWithDup = function (nums) {
    nums.sort((a, b) => a - b);
    const len = nums.length;

    const vis = new Array(len).fill(false);
    const res = [];

    const backtrack = (path, index) => {
        if (path.length > len) return;
        res.push(Array.from(path));
        for (let i = index; i < len; i++) {
            if (i > 0 && nums[i] == nums[i - 1] && vis[i - 1] == false) continue;
            path.push(nums[i]);
            vis[i] = true;
            backtrack(path, i + 1);
            path.pop();
            vis[i] = false;
        }
    };
    backtrack([], 0);
    return res;
};
console.log(subsetsWithDup([1, 2, 2]));
